package data_structure.mooc;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树：根节点 左孩子 右孩子 叶子节点
 * 平衡二叉树：当前节点的值大于所有左孩子节点的值，小于所有右孩子节点的值
 * 添加元素
 * 深度遍历
 * 广度遍历
 * @param <E>
 */
public class BST<E extends Comparable<E>> {

    /**
     * 内部存储的元素
     */

    private class Node{
        public E value;
        public Node left;
        public Node right;

        public Node(E value){
            this.value = value;
            this.left = null;
            this.right=null;
        }
    }
    public Node root;//根节点
    public int size;

    public BST(Node root){
        this.root = root;
        size = 0;
    }

    public BST(){
        this.size = 0;
        this.root=null;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 递归添加元素
     * @param value
     */
    public void add(E value){
        root=add(root,value);
    }

    /**
     * 向根节点为node的二叉树中添加元素
     * @param node
     * @param value
     * @return
     */
    private Node add(Node node,E value){
//       一个优雅的设计，无论是刚开始向二叉树中添加元素，还是完成搜索后添加元素，元素插入的位置原来都是空的
        if(node==null){
            node=new Node(value);
            size++;
        }
        if(value.compareTo(node.value)<0){
            node.left=add (node.left,value);
        }else if(value.compareTo(node.value) > 0){
            node.right=add (node.right,value);
        }
        return node;
    }

    /**
     * 非递归添加元素
     * @param value
     */

    public void addNR(E value){

        if(root==null){
            size++;
            root=new Node(value);
            return;
        }

        Node curr=root;
        while(curr!=null){
            if(value.compareTo(curr.value) < 0){
                if(curr.left == null){
                    curr.left=new Node (value);
                    size++;
                    return;
                }
                curr=curr.left;
            }else if(value.compareTo(curr.value) > 0){
                if (curr.right == null) {
                    curr.right = new Node(value);
                    size++;
                    return;
                }
                curr=curr.right;
            }else{
                return;
            }
        }
    }

    /**
     * 搜索二叉树中是否包好指定值
     * @param e
     * @return
     */
    public boolean contains(E e){
        return contains (root,e);
    }

    /**
     * 搜索以root为根节点的二叉树中是否包含指定值
     * @param root
     * @param e
     * @return
     */
    private boolean contains(Node root, E e) {

        if(root==null){
            return false;
        }
        if(e.compareTo (root.value)==0)return true;
        if(e.compareTo(root.value) < 0){
            return contains (root.left,e);
        }else{
            return contains(root.right, e);
        }
    }

    /**
     * 前序非递归遍历二叉树
     */
    public void preOrderNR(){
        preOrderNR (root);
    }

    private void preOrderNR(Node node) {
        Stack<Node>stack = new Stack<> ();
        stack.add (node);
        Node temp=null;
        while(!stack.isEmpty()){
            temp=stack.pop();
            System.out.println(temp.value);
            if(temp.right != null)stack.push(temp.right);
            if(temp.left != null)stack.push(temp.left);
        }
    }

    /**
     * 中序非递归遍历二叉树
     */
    public void inOrderNR(){
        inOrderNR (root);
    }

    private void inOrderNR(Node node) {
        Stack<Node>stack = new Stack<> ();
        Node curr=node;
        while(curr!=null){
            stack.push (curr);
            curr=curr.left;
        }
        while(!stack.isEmpty()){
            curr=stack.pop ();
            System.out.println(curr.value);
            if(curr.right != null){
                curr=curr.right;
                while(curr!=null){
                    stack.push (curr);
                    curr = curr.left;
                }
            }
        }
    }

    /**
     * 后序非递归遍历二叉树
     */
   public void postOrderNR(){

        if(root==null)return;
        Node curr=root;
        //用来将数组转化为书的节点
        Stack<Node>stack = new Stack<> ();
        //暂时用来存储树的左孩子
        Stack<Node>stack2 = new Stack<> ();

        while(curr!=null){
            stack.push(curr);
            curr=curr.left;
        }
        //栈不为空时，输出元素
        while(!stack.isEmpty()){
           Node temp=stack.peek ();
            //temp.right==null;
            if(temp.right==null){
                System.out.println(stack.pop().value);
            }else if(!stack2.isEmpty ()&&stack2.peek().value ==stack.peek().value){
                stack2.pop ();
                System.out.println(stack.pop().value);
            }//temp.right!=null时，以temp.right为根节点开始遍历左子树
            //使用stack2记录分支节点
            else if(temp.right != null){
                stack2.push(temp);
                temp=temp.right;
                while(temp!=null){
                    stack.push(temp);
                    temp=temp.left;
                }
            }
        }
    }

    /**
     * 前序递归遍历二叉树
     */
    public void preOrder(){
        preOrder (root);
    }

    private void preOrder(Node node){
        if(node==null)return;
        System.out.println(node.value);
        preOrder (node.left);
        preOrder (node.right);
    }

    /**
     * 中序递归遍历二叉树
     */
    public void inOrder(){
        inOrder (root);
    }
    private void inOrder(Node node){
        if(node==null)return;
        inOrder (node.left);
        System.out.println(node.value);
        inOrder(node.right);
    }

    /**
     * 后序递归遍历二叉树
     */
    public void postOrder(){
        postOrder (root);
    }
    private void postOrder(Node node){

        if(node == null)return;
        postOrder (node.left);
        postOrder(node.right);
        System.out.println(node.value);
    }

    /**
     * 层序遍历
     */
    public void leverOrder(){
        leverOrder (root);
    }

    private void leverOrder(Node node){
        Queue<Node>queue =new LinkedList<> ();
        queue.add(node);
        while(!queue.isEmpty()){
            Node curr=queue.poll();
            System.out.println(curr.value);
            if(curr.left!=null){
                queue.add(curr.left);
            }
            if(curr.right!=null){
                queue.add(curr.right);
            }
        }
    }

    /**
     * 递归层序遍历
     */
    public void leverOrderN(){
        System.out.println(root.value);
        leverOrderN (root);
    }
    private void leverOrderN(Node node){
        if(node==null)return;
//        node.left
//        node.right
        if(node.left != null){
            System.out.println(node.left.value);
        }
        if(node.right != null){
            System.out.println(node.right.value);
        }
        leverOrderN (node.left);
        leverOrderN (node.right);
    }

    /**
     *
     * @return
     */
    public Node minNode(){
        return minNode (root);
    }

    private Node minNode(Node root) {

        if(root.left==null)return root;
        return minNode (root.left);
    }
    public Node maxNode(){
        return maxNode (root);
    }

    private Node maxNode(Node root) {

        if(root.right==null)return root;
        return maxNode (root.right);
    }

    /**
     * 删除最小节点
     * @return
     */
    public E removeMin(){
       E ret=minNode (root).value;
       removeMin (root);
       return ret;
    }

    /**
     * 返回删除最小节点后的新节点
     * @param node
     * @return
     */
    private Node removeMin(Node node) {

        //删除node节点，node.left=null,node.right=null,size--,返回删除node节点后的节点
        if(node.left==null){
            Node rightNode=node.right;
            node.right=null;
            size--;
            return rightNode;
        }

        //删除最小节点后的新节点作为当前节点的左子树,node.right的值依然还是小于node
        node.left=removeMin (node.left);
        return node;
    }

    /**
     * 删除二叉树中最大的节点
     * @return
     */
    public E removeMax(){
        E ret=maxNode (root).value;
        removeMax (root);
        return ret;
    }

    /**
     * 返回删除最大节点后的根节点
     * @param node
     * @return
     */
    private Node removeMax(Node node){

        if(node.right == null){
            Node leftNode=node.left;
            node.left=null;
            size--;
            return leftNode;
        }

        node.right=removeMax (node.right);
        return node;
    }

    /**
     * 删除二叉树中指定的值
     * @param e
     */
    public void remove(E e){
        root=remove(root,e);
    }

    /**
     * 返回删除指定值后二叉树的根节点
     * @param node
     * @param e
     * @return
     */
    private Node remove(Node node, E e) {
        //找不到时，返回null;
        if(node==null){
            return null;
        }
        //从根节点开始往下面找
        if(e.compareTo (node.value)<0){
            node.left=remove (node.left,e);
            return node;
        }else if(e.compareTo(node.value) > 0){
            node.right = remove(node.right, e);
            return node;
        }else{//e==node.value
            //代表找到套删除的节点
            //注意分情况讨论
//1.待删除节点的左子树为空
            if(node.left==null){
                Node rightNode=node.right;
                node.right=null;
                size--;
                return rightNode;
            }
//2.待删除节点的右子树为空
            if(node.right==null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
//3，待删除节点的左右子树均不为空
           /**
             *左右孩子均不为空时
             *选择当前节点的右子树的最小节点作为前驱
             *前驱大于当前节点左子树的的所有值，小于当前节点右子树的所有值
             *具体操作，使用removeMin()方法删除先删除前驱，再将前驱作为当前子树的根节点返回
             */
            Node successor=minNode (root.right);
            Node delNode=removeMin(root.right);
            successor.left=root.left;
            successor.right =delNode;
            root.right=root.left=null;
            return successor;
        }
    }


    @Override
    public String toString() {

        StringBuilder sb = new StringBuilder();
        generatorBSTString(root,sb,1);
        return sb.toString ();
    }

    private void generatorBSTString(Node root, StringBuilder sb,int depth){
        if(root==null){
            sb.append (generatorDepth (depth)+"null\n");
            return;
        }
        sb.append((generatorDepth (depth)+root.value)+"\n");
        generatorBSTString (root.left,sb,depth+1);
        generatorBSTString (root.right,sb,depth+1);
    }

    private String generatorDepth(int depth){
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append ("-");
        }
        return sb.toString ();
    }

    public static void main(String[] args) {
        BST<Integer>bst=new BST<Integer> (null);
        Integer []arr=new Integer[]{14,11,42,10,12,20,46};
        for (int i = 0; i < arr.length; i++) {
            bst.addNR (arr[i]);
        }
        bst.remove(42);
        System.out.println("------");
        bst.inOrder ();
        System.out.println (bst.toString ());
    }
}
